{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NvFMw17BoLbq"
      },
      "source": [
        "##### Copyright 2020 Google"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "CvJ_QrYPoM8L"
      },
      "outputs": [],
      "source": [
        "#@title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
        "# you may not use this file except in compliance with the License.\n",
        "# You may obtain a copy of the License at\n",
        "#\n",
        "# https://www.apache.org/licenses/LICENSE-2.0\n",
        "#\n",
        "# Unless required by applicable law or agreed to in writing, software\n",
        "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
        "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
        "# See the License for the specific language governing permissions and\n",
        "# limitations under the License."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5No0RIEdnI9l"
      },
      "source": [
        "# QAOA example problems"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OYeSZNZBoUK2"
      },
      "source": [
        "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://www.example.org/cirq/experiments/qaoa/example_problems\"><img src=\"https://www.tensorflow.org/images/tf_logo_32px.png\" />View on QuantumLib</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/ReCirq/blob/master/docs/qaoa/example_problems.ipynb\"><img src=\"https://www.tensorflow.org/images/colab_logo_32px.png\" />Run in Google Colab</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://github.com/quantumlib/ReCirq/blob/master/docs/qaoa/example_problems.ipynb\"><img src=\"https://www.tensorflow.org/images/GitHub-Mark-32px.png\" />View source on GitHub</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a href=\"https://storage.googleapis.com/tensorflow_docs/ReCirq/docs/qaoa/example_problems.ipynb\"><img src=\"https://www.tensorflow.org/images/download_logo_32px.png\" />Download notebook</a>\n",
        "  </td>\n",
        "</table>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rlV2faqhnI9n"
      },
      "source": [
        "The shallowest depth version of the Quantum Approximate Optimization Algorithm (QAOA) consists of the application of two unitary operators: the problem unitary and the driver unitary. The first of these depends on the parameter $\\gamma$ and applies a phase to pairs of bits according to the problem-specific cost operator $C$:\n",
        "\n",
        "$$\n",
        "    U_C \\! \\left(\\gamma \\right) = e^{-i \\gamma C } = \\prod_{j < k} e^{-i \\gamma w_{jk} Z_j Z_k}\n",
        "$$\n",
        "\n",
        "whereas the driver unitary depends on the parameter $\\beta$, is problem-independent, and serves to drive transitions between bitstrings within the superposition state:\n",
        "\n",
        "$$\n",
        "    \\newcommand{\\gammavector}{\\boldsymbol{\\gamma}}\n",
        "    \\newcommand{\\betavector}{\\boldsymbol{\\beta}}\n",
        "    U_B \\! \\left(\\beta \\right) = e^{-i \\beta B} = \\prod_j e^{- i \\beta X_j},\n",
        "    \\quad \\qquad\n",
        "    B = \\sum_j X_j\n",
        "$$\n",
        "\n",
        "where $X_j$ is the Pauli $X$ operator on qubit $j$. These operators can be implemented by sequentially evolving under each term of the product; specifically the problem unitary is applied with a sequence of two-body interactions while the driver unitary is a single qubit rotation on each qubit. For higher-depth versions of the algorithm the two unitaries are sequentially re-applied each with their own $\\beta$ or $\\gamma$. The number of applications of the pair of unitaries is represented by the hyperparameter $p$ with parameters  $\\gammavector = (\\gamma_1, \\dots, \\gamma_p)$ and $\\betavector = (\\beta_1, \\dots, \\beta_p)$. For $n$ qubits, we prepare the parameterized state\n",
        "\n",
        "$$\n",
        "    \\newcommand{\\bra}[1]{\\langle #1|}\n",
        "    \\newcommand{\\ket}[1]{|#1\\rangle}\n",
        "    | \\gammavector , \\betavector \\rangle = U_B(\\beta_p)  U_C(\\gamma_p ) \\cdots U_B(\\beta_1) U_C(\\gamma_1 ) \\ket{+}^{\\otimes n},\n",
        "$$\t\t\n",
        "where $\\ket{+}^{\\otimes n}$ is the symmetric superposition of computational basis states.\n",
        "\n",
        "<img src=\"./images/qaoa_circuit.png\" alt=\"QAOA circuit\"/>\n",
        "\n",
        "The optimization problems we study in this work are defined through a cost function with a corresponding quantum operator C given by\n",
        "\n",
        "$$\n",
        "    C  =  \\sum_{j < k}  w_{jk}  Z_j  Z_k\n",
        "$$\n",
        "\n",
        "where $Z_j$ dnotes the Pauli $Z$ operator on qubit $j$, and the $w_{jk}$ correspond to scalar weights with values $\\{0, \\pm1\\}$. Because these clauses act on at most two qubits, we are able to associate a graph with a given problem instance with weighted edges given by the $w_{jk}$ adjacency matrix."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DOK-LOEon_oz"
      },
      "source": [
        "## Setup\n",
        "\n",
        "Install the ReCirq package:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "U7mt9RdZoAht"
      },
      "outputs": [],
      "source": [
        "try:\n",
        "    import recirq\n",
        "except ImportError:\n",
        "    !pip install git+https://github.com/quantumlib/ReCirq"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EAlsSqqyoDMj"
      },
      "source": [
        "Now import Cirq, ReCirq and the module dependencies:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "nik2_FnVnI9o"
      },
      "outputs": [],
      "source": [
        "import networkx as nx\n",
        "import numpy as np\n",
        "import scipy.optimize\n",
        "import cirq\n",
        "import recirq\n",
        "\n",
        "%matplotlib inline\n",
        "from matplotlib import pyplot as plt"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ii5SmPcAnI9u"
      },
      "outputs": [],
      "source": [
        "# theme colors\n",
        "QBLUE = '#1967d2'\n",
        "QRED = '#ea4335ff'\n",
        "QGOLD = '#fbbc05ff'"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "187A1F4unI9y"
      },
      "source": [
        "## Hardware grid\n",
        "\n",
        "First, we study problem graphs which match the connectivity of our hardware, which we term \"Hardware Grid problems\". Despite results showing that problems on such graphs are efficient to solve on average, we study these problems as they do not require routing. This family of problems is composed of random instances generated by sampling $w_{ij}$ to be $\\pm 1$ for edges in the device topology or a subgraph thereof."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "cfqQ04KknI9z"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problems import get_all_hardware_grid_problems\n",
        "import cirq.contrib.routing as ccr\n",
        "\n",
        "hg_problems = get_all_hardware_grid_problems(\n",
        "    device_graph=ccr.gridqubits_to_graph_device(recirq.get_device_obj_by_name('Sycamore23').qubits),\n",
        "    central_qubit=cirq.GridQubit(6,3),\n",
        "    n_instances=10,\n",
        "    rs=np.random.RandomState(5)\n",
        ")   \n",
        "\n",
        "instance_i = 0\n",
        "n_qubits = 23\n",
        "problem = hg_problems[n_qubits, instance_i]\n",
        "\n",
        "fig, ax = plt.subplots(figsize=(6,5))\n",
        "pos = {i: coord for i, coord in enumerate(problem.coordinates)}\n",
        "nx.draw_networkx(problem.graph, pos=pos, with_labels=False, node_color=QBLUE)\n",
        "if True:  # toggle edge labels\n",
        "    edge_labels = {(i1, i2): f\"{weight:+d}\"\n",
        "                   for i1, i2, weight in problem.graph.edges.data('weight')}\n",
        "    nx.draw_networkx_edge_labels(problem.graph, pos=pos, edge_labels=edge_labels)\n",
        "ax.axis('off')\n",
        "fig.tight_layout()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QLolw23UnI93"
      },
      "source": [
        "## Sherrington-Kirkpatrick model\n",
        "\n",
        "Next, we study instances of the Sherrington-Kirkpatrick (SK) model, defined on the complete graph with $w_{ij}$ randomly chosen to be $\\pm 1$. This is a canonical example of a frustrated spin glass and is most penalized by routing, which can be performed optimally using the linear swap networks at the cost of a linear increase in circuit depth. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Cuo5ICa7nI94"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problems import get_all_sk_problems\n",
        "\n",
        "n_qubits = 17\n",
        "all_sk_problems = get_all_sk_problems(max_n_qubits=17, n_instances=10, rs=np.random.RandomState(5))\n",
        "sk_problem = all_sk_problems[n_qubits, instance_i]\n",
        "\n",
        "fig, ax = plt.subplots(figsize=(6,5))\n",
        "pos = nx.circular_layout(sk_problem.graph)\n",
        "nx.draw_networkx(sk_problem.graph, pos=pos, with_labels=False, node_color=QRED)\n",
        "if False:  # toggle edge labels\n",
        "    edge_labels = {(i1, i2): f\"{weight:+d}\"\n",
        "                   for i1, i2, weight in sk_problem.graph.edges.data('weight')}\n",
        "    nx.draw_networkx_edge_labels(sk_problem.graph, pos=pos, edge_labels=edge_labels)\n",
        "ax.axis('off')\n",
        "fig.tight_layout()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XiGuaxqCnI97"
      },
      "source": [
        "## 3-regular MaxCut\n",
        "\n",
        "Finally, we study instances of the MaxCut problem on 3-regular graphs. This is a prototypical discrete optimization problem with a low, fixed node degree but a high dimension which cannot be trivially mapped to a planar architecture. It more closely matches problems of industrial interest. For these problems, we use an automated routing algorithm to heuristically insert SWAP operations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qiPswoVpnI98"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problems import get_all_3_regular_problems\n",
        "\n",
        "n_qubits = 22\n",
        "instance_i = 0\n",
        "threereg_problems = get_all_3_regular_problems(max_n_qubits=22, n_instances=10, rs=np.random.RandomState(5))\n",
        "threereg_problem = threereg_problems[n_qubits, instance_i]\n",
        "\n",
        "fig, ax = plt.subplots(figsize=(6,5))\n",
        "pos = nx.spring_layout(threereg_problem.graph, seed=11)\n",
        "nx.draw_networkx(threereg_problem.graph, pos=pos, with_labels=False, node_color=QGOLD)\n",
        "if False:  # toggle edge labels\n",
        "    edge_labels = {(i1, i2): f\"{weight:+d}\"\n",
        "                   for i1, i2, weight in threereg_problem.graph.edges.data('weight')}\n",
        "    nx.draw_networkx_edge_labels(threereg_problem.graph, pos=pos, edge_labels=edge_labels)\n",
        "ax.axis('off')\n",
        "fig.tight_layout()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "example_problems.ipynb",
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
